package demo1;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
        public int pileBox(int[][] box) {
            Arrays.sort(box,(i, j)->{
                return i[0]-j[0];
            });
            int n = box.length;
            int[] dp = new int[n];
            for (int i = 0; i < n; i++) {
                dp[i] = box[i][2];
            }
            int ret = 0;
            for (int i = 0; i < n; i++) {
                int max = dp[i];
                for (int j = 0; j < i; j++) {
                    if(box[i][0]>box[j][0] && box[i][1]>box[j][1] && box[i][2]>box[j][2]){
                        max = Math.max(max,dp[j]+dp[i]);
                    }
                }
                dp[i] = max;
                ret = Math.max(ret,max);
            }
            return ret;
        }

        //俄罗斯套娃信封问题
        public int maxEnvelopes(int[][] envelopes) {
            Arrays.sort(envelopes,(i,j)->{
                if(i[0]==j[0]){
                    return j[1]-i[1];
                }
                return i[0]-j[0];
            });
            int len = envelopes.length;
            int[] ret = new int[len];
            ret[0] = envelopes[0][1];
            int size = 1;
            for (int i = 1; i < len; i++) {
                size = merg(ret,envelopes[i][1],size);
            }
            return size;
        }

        private int merg(int[] nums,int key,int size){
            int left = 0;int right = size-1;
            while (left < right) {
                int mid = left+(right-left)/2;
                if(nums[mid]<key) left = mid+1;
                else right = mid;
            }
            if(nums[left]<key && left==size-1){
                nums[left+1] = key;
                return size+1;
            }
            nums[left] = key;
            return size;
        }

        public int maxEnvelopes1(int[][] envelopes) {
            Arrays.sort(envelopes,(i,j)->{
                return i[0]-j[0];
            });
            int n = envelopes.length;
            int[] dp = new int[n];
            Arrays.fill(dp,1);
            dp[0] = 1;
            int MAX = 0;
            for (int i = 1; i < n; i++) {
                int max = Integer.MIN_VALUE;
                for (int j = 0; j < i; j++) {
                    if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
                        max = Math.max(max,dp[j]);
                    }
                }
                dp[i] = max+1;
                MAX = Math.max(MAX,dp[i]);
            }
            return MAX;
        }

        //K次乘运算后的最终数组1
        public int[] getFinalState(int[] nums, int k, int multiplier) {
            int n = nums.length;
            int minIndex = 0;
            for (int i = 0; i < k; i++) {
                minIndex = 0;
                for (int j = 0; j < n; j++) {
                    if(nums[minIndex]>nums[j]){
                        minIndex = j;
                    }
                }
                nums[minIndex] *= multiplier;
            }
            return nums;
        }
}
